/**
 * 给定一个整数，将其数位的0去掉，剩下的称为结果
 * 统计[1, N]之间不同结果的数量
 * 
 * 令Di表示数位长度为i + 1的答案，显然 Di = 9 ^ i
 * 
 * 令N的数位长度为L，假设N包含了0，则答案就是 SIGMA{Di, i从0到L-1}
 * 如果N的每个数位都不包含0，做一个数位DP的深搜即可
 * 用一个全局Set，记录是否重复
 */
using llt = long long;
llt D[17];

set<llt> Set;
vector<int> G;

llt dfs(int pos, llt now, bool lead, bool limit){
    if(-1 == pos){
        auto it = Set.find(now);
        if(it == Set.end()){
            it = Set.emplace_hint(it, now);
            return 1;
        }
        return 0;
    }
    if(not lead and not limit){
        return D[pos];
    }
    llt ans = 0;
    int last = limit ? G[pos] : 9;
    for(int i=1;i<=last;++i){
        ans += dfs(pos - 1, now * 10 + i, false, limit&&last==i);
    }
    return ans;
}

class Solution {
public:
    long long countDistinct(long long n) {
        D[0] = 9;
        for(int i=1;i<17;++i) D[i] = D[i - 1] * 9;

        G.clear();
        Set.clear();
        bool has0 = false;
        while(n){
            G.push_back(n % 10);
            n /= 10;
            if(G.back() == 0) has0 == true;
        }

        int sz = G.size();
        if(1 == sz) return G.back();
        llt ans = 0;
        for(int i=0;i<sz-1;++i) ans += D[i];
        if(has0) return ans;
        ans += dfs(sz - 1, 0, true, true);
        return ans;
    }
};